package com.hiwhitley.leetcode.hard;

/**
 * Created by hiwhitley on 16-12-29.
 */
public class TrappingRainWater_42 {
    public int trap(int height[]) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int n = height.length;
        int LMAX = height[0];// 左边最大值
        int RMAX = height[n - 1];// 右边最大值
        int sum = 0;
        int L = 1;
        int R = n - 2;
        while (L <= R) {
            if (LMAX <= RMAX) {
                sum += Math.max(LMAX - height[L], 0);
                LMAX = Math.max(LMAX, height[L++]);
            } else {
                sum += Math.max(RMAX - height[R], 0);
                RMAX = Math.max(RMAX, height[R--]);
            }
        }
        return sum;
    }
}
